#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs)
    {
        sort(pairs.begin(), pairs.end());  // 先排序，保证 pairs[x][1] 递增
        int n = pairs.size();
        int len = 0;
        vector<int> temp(n, 0);
        for (int i = 0; i < pairs.size(); i++) {
            if (!len || pairs[i][0] > temp[len - 1]) {
                temp[len++] = pairs[i][1];
            } else {
                int low = 0, high = len;
                while (low < high) {
                    int mid = low + (high - low) / 2;
                    if (temp[mid] > pairs[i][1]) {
                        high = mid;
                    } else {
                        low = mid + 1;
                    }
                }
                temp[low] = pairs[i][1]; 
            }
        }
        return len;
    }
};

/**
 * @date 2022-09-03
 * @brief lis 的贪心 + 二分做法
 */